package collection;

import java.util.Comparator;
import java.util.Iterator;
import java.util.Random;

import exception.CollectionEmptyException;

public class BinarySearchTree<K,V> extends BinTree<Entry<K,V>> {

	private Comparator<K> comp;
	
	public BinarySearchTree(Comparator<K> comp)
	{
		this.comp = comp;
	}
	
	public BinTreeNode<Entry<K,V>> searchNodeByKey(K key, BinTreeNode<Entry<K,V>> node)
	{
		if (node==null)
			throw new IllegalArgumentException("Called with null: key = " + key);
		
		if (isExternal(node))
		{
			return node;
		}
		
		if (comp.compare(key, node.getElement().getKey()) == 0)
		{
			return node;
		}
		else if (comp.compare(key, node.getElement().getKey()) < 0)
		{
			if (getLeftChild(node) == null)
				return node;
			else
				return searchNodeByKey(key, getLeftChild(node));
		}
		else
		{
			if (getRightChild(node) == null)
				return node;
			else
				return searchNodeByKey(key, getRightChild(node));
		}
	}
	
	public Entry<K,V> findEntry(K key, BinTreeNode<Entry<K,V>> node)
	{
		BinTreeNode<Entry<K,V>> foundNode = searchNodeByKey(key, node);
		
		if (foundNode.getElement().getKey().equals(key))
		{
			return foundNode.getElement();
		}
		else
		{
			return null;
		}
	}
	
	public Entry<K,V> findEntry(K key)
	{
		if (!isEmpty())
			return findEntry(key, getRoot());
		else
			throw new CollectionEmptyException("Binary Search Tree");
	}
	
	public void insertEntry(Entry<K,V> entry, BinTreeNode<Entry<K,V>> node)
	{
		BinTreeNode<Entry<K,V>> foundNode = searchNodeByKey(entry.getKey(), node);
		Entry<K,V> foundEntry = foundNode.getElement();
	
		if (foundEntry.equals(entry))
			return ;

		if (isExternal(foundNode))
		{
			BinTreeNode<Entry<K,V>> newNode = createNode(entry);
			if (comp.compare(foundEntry.getKey(), entry.getKey()) > 0)
			{
				foundNode.setLeftChild(newNode);
				newNode.setParent(foundNode);
			}
			else
			{
				foundNode.setRightChild(newNode);
				newNode.setParent(foundNode);
			}
			super.size += 1;
		}
		else
		{
			if (foundNode.getLeftChild() != null && foundNode.getRightChild() != null)
			{
				Random randomGen = new Random();
				boolean goLeft = randomGen.nextInt(2)==0 ? true : false;
				if (goLeft) 
				{
					insertEntry(entry, foundNode.getLeftChild());
				} 
				else 
				{
					insertEntry(entry, foundNode.getRightChild());
				}
			}
			else if (foundNode.getLeftChild() == null)
			{
				BinTreeNode<Entry<K,V>> newNode = createNode(entry);
				foundNode.setLeftChild(newNode);
				newNode.setParent(foundNode);
				super.size += 1;
			}
			else if (foundNode.getRightChild() == null)
			{
				BinTreeNode<Entry<K,V>> newNode = createNode(entry);
				foundNode.setRightChild(newNode);
				newNode.setParent(foundNode);
				super.size += 1;
			}
		}
	}
	
	public void insertEntry(Entry<K,V> entry)
	{
		if (!isEmpty())
			insertEntry(entry, getRoot());
		else
			createRoot(entry);
	}
	
	private void swapNodeForRemove(BinTreeNode<Entry<K,V>> foundNode, boolean goLeft)
	{
		BinTreeNode<Entry<K,V>> nodeToSwap = null;
		if (goLeft)
		{
			nodeToSwap = foundNode.getLeftChild();
			while(nodeToSwap.getRightChild() != null)
			{
				nodeToSwap = nodeToSwap.getRightChild();
			}
			if (nodeToSwap.getLeftChild() != null)
			{
				foundNode.setElement(nodeToSwap.getElement());
				removeEntry(nodeToSwap.getElement(), nodeToSwap);
			}
			else
			{
				foundNode.setElement(nodeToSwap.getElement());
				removeNode(nodeToSwap);
				super.size -= 1;
			}
		}
		else
		{
			nodeToSwap = foundNode.getRightChild();
			while(nodeToSwap.getLeftChild() != null)
			{
				nodeToSwap = nodeToSwap.getLeftChild();
			}
			if (nodeToSwap.getRightChild() != null)
			{
				foundNode.setElement(nodeToSwap.getElement());
				removeEntry(nodeToSwap.getElement(), nodeToSwap);
			}
			else
			{
				foundNode.setElement(nodeToSwap.getElement());
				removeNode(nodeToSwap);
				super.size -= 1;
			}
		}
	}
	
	public void removeEntry(Entry<K,V> entry, BinTreeNode<Entry<K,V>> node)
	{
		BinTreeNode<Entry<K,V>> foundNode = searchNodeByKey(entry.getKey(), node);
		Entry<K,V> foundEntry = foundNode.getElement();
		
		if (isExternal(foundNode))
		{
			if (foundNode.getElement().equals(entry))
			{
				removeNode(foundNode);
			}
			super.size -= 1;
		}
		else
		{
			if (foundEntry.equals(entry))
			{
				if (foundNode.getLeftChild() != null && foundNode.getRightChild() != null)
				{
					Random randomGen = new Random();
					boolean goLeft = randomGen.nextInt(2)==0 ? true : false;
					if (goLeft)
					{
						swapNodeForRemove(foundNode, true);
					}
					else
					{
						swapNodeForRemove(foundNode, false);
					}
				}
				else if(foundNode.getLeftChild() != null)
				{
					swapNodeForRemove(foundNode, true);
				}
				else if (foundNode.getRightChild() != null)
				{
					swapNodeForRemove(foundNode, false);
				}
			}
			else
			{
				if (foundNode.getLeftChild() != null)
				{
					removeEntry(entry, foundNode.getLeftChild());
				}
				if (foundNode.getRightChild() != null)
				{
					removeEntry(entry, foundNode.getRightChild());
				}
			}
		}
	}
	
	public void removeEntry(Entry<K,V> entry)
	{
		if (!isEmpty())
			removeEntry(entry, getRoot());
		else
			throw new CollectionEmptyException("Binary Search Tree");
	}
	
	public SLinkedList<Entry<K,V>> findAllEntries(K key, BinTreeNode<Entry<K,V>> node)
	{
		SLinkedList<Entry<K,V>> entries = new SLinkedList<Entry<K,V>>();
		BinTreeNode<Entry<K,V>> foundNode = searchNodeByKey(key, node);
		Entry<K,V> foundEntry = foundNode.getElement();

		if (isExternal(foundNode))
		{
			if (foundEntry.getKey().equals(key))
			{
				entries.addLast(entries.createNode(foundEntry));
			}
		}
		else
		{	
			if (foundEntry.getKey().equals(key))
			{
				entries.addLast(entries.createNode(foundEntry));
			}
			if (foundNode.getLeftChild() != null)
			{
				Iterator<Entry<K,V>> entriesIterInLeftSubTree = findAllEntries(key, foundNode.getLeftChild()).elementsIterator();
				while(entriesIterInLeftSubTree.hasNext())
				{
					entries.addLast(entries.createNode(entriesIterInLeftSubTree.next()));
				}
			}
			if (foundNode.getRightChild() != null)
			{
				Iterator<Entry<K,V>> entriesIterInRightSubTree = findAllEntries(key, foundNode.getRightChild()).elementsIterator();
				while(entriesIterInRightSubTree.hasNext())
				{
					entries.addLast(entries.createNode(entriesIterInRightSubTree.next()));
				}
			}
			
		}
		
		return entries;
	}
	
	public SLinkedList<Entry<K,V>> findAllEntries(K key)
	{
		if (!isEmpty())
			return findAllEntries(key, getRoot());
		else
			throw new CollectionEmptyException("Binary Search Tree");
	}

	public Iterator<Entry<K, V>> elementsIterator() 
	{
		final SLinkedList<Entry<K,V>> entries = new SLinkedList<Entry<K,V>>();
		if (isEmpty())
		{
			return entries.elementsIterator();
		}
		else
		{
			inOrderTraverse(getRoot(), new ANodeCommand<Entry<K,V>>(){

				@Override
				public void applyToElement(Entry<K, V> element) 
				{
					entries.addLast(entries.createNode(element));
				}
				
			});
			
			return entries.elementsIterator();
		}
	}
}
